module stack_mod
   implicit none
   type node_t
      character(len=:),allocatable::val
      type(node_t),allocatable::next
   end type node_t

   type stack
      type(node_t),allocatable::tail
   contains
      procedure::push
      procedure::get
      procedure::pop
      procedure::empty
      procedure::reverse
   end type stack
contains
   subroutine push(this,val_)
      class(stack),intent(inout) ::this
      character(len=*),intent(in)::val_
      type(node_t),allocatable   ::new
      allocate(new)
      new%val=trim(val_)
      call move_alloc(this%tail,new%next)
      call move_alloc(new,this%tail)
   end subroutine push

   function pop(this)result(res)
      class(stack),intent(inout)::this
      character(len=:),allocatable::res
      type(node_t),allocatable::tmp
      res=this%tail%val
      call move_alloc(this%tail%next,tmp)
      deallocate(this%tail)
      call move_alloc(tmp,this%tail)
   end function pop

   function get(this)result(res)
      class(stack),intent(inout)::this
      character(len=:),allocatable::res
      res=this%tail%val
   end function get

   logical function empty(this)result(res)
      class(stack),intent(inout)::this
      res=.not.allocated(this%tail)
   end function empty

   subroutine reverse(this)
      class(stack),intent(inout)::this
      type(stack)::tmp
      do while(.not.this%empty())
         call tmp%push(this%pop())
      end do
      call move_alloc(tmp%tail,this%tail)
   end subroutine reverse
end module stack_mod